package mytest;

public class Test2 {

	static int[] arr={1111,23,3,3,3,3,30,2,5,712,4,5,9};
	
	
	static void heapAdjust(int k,int end)
	{
		int data=arr[k],cur=2*k+1,p=k;
		while(cur<end)
		{
			if(cur+1<end&&arr[cur]<arr[cur+1])cur=cur+1;
			if(data<arr[cur]){arr[p]=arr[cur];
			p=cur;
			cur=cur*2+1;
			}else break;
		}
		arr[p]=data;
	}
	
	
	static void heapSort()
	{
		for(int i=arr.length/2-1;i>=0;i--)
			heapAdjust(i,arr.length);
		for(int i=0;i<arr.length;i++)
		{
			int tmp=arr[0];
			arr[0]=arr[arr.length-i-1];
			arr[arr.length-i-1]=tmp;
			heapAdjust(0,arr.length-i-1);
		}
	}
	
	
	static boolean countSort(int k)
	{
		boolean finish=true;
		int high=1,low=1;
		for(int i=0;i<k;i++){low=high;high*=10;}
		int [] b=new int[10];
		for(int i=0;i<arr.length;i++)
		{
			int cur=(arr[i]%high)/low;
			if(cur!=0&&finish){
				finish=false;
			}
			b[cur]++;
		}
		if(finish)return true;
		
		for(int i=1;i<b.length;i++)b[i]+=b[i-1];
		
		int[] result=new int[arr.length];
		for(int i=arr.length-1;i>=0;i--)
		{
			int cur=(arr[i]%high)/low;
			int pos=b[cur];
			b[cur]--;
			result[pos-1]=arr[i];
		}
		arr=result;
		return false;
	}
	
	static void radixSort()
	{
		for(int i=1;;i++)
		{
			
			if(countSort(i))break;
			System.out.println(i+":");
			for(int j=0;j<arr.length;j++)
			{
				System.out.print(arr[j]+" ");
			}
			System.out.println();
		}
	}
	
	static void mergeSort(int i,int j)
	{
		if(i<j)
		{
			int mid=(i+j)>>1;
			mergeSort(i,mid);
			mergeSort(mid+1,j);
			merge(i,mid,j);
		}
	}
	
	static void merge(int start,int mid,int end)
	{
		int t[]=new int[end-start+1];
		int i=start,j=mid+1,k=0;
		while(i<=mid&&j<=end)
		{
			if(arr[i]<arr[j])
			{
				t[k++]=arr[i];
				i++;
			}else{
				t[k++]=arr[j];
				j++;
			}
		}
		while(i<=mid)
		{
			t[k++]=arr[i];i++;
		}
		while(j<=end)
		{
			t[k++]=arr[j];j++;
		}
		System.arraycopy(t, 0, arr, start, end-start+1);
	}
	
	
	static void print()
	{
		for(int j=0;j<arr.length;j++)
		{
			System.out.print(arr[j]+" ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		
		//heapSort();
		//radixSort();
		print();
		mergeSort(0, arr.length-1);
		print();
	}
}
